#include "TED.h"

int Minimum(const int a,const int b,const int c)
{
	if(a<=b && a<=c)
		return a;
	if(b<=a && b<=c)
		return b;
	else
		return c;
}

TED::TED(Tree* F1,Tree* G1,Distance* distance1, Algorithm algorithm1)
{
	algorithm = algorithm1;
	if(distance1 != NULL)
		distance = distance1;
	else
	{
		distance = new Distance();
	}
	//calculate the size of each tree via a post order traversal
	F1->Postorder();
	G1->Postorder();
	//calculate the delete cost of each tree
	distance->UpdateTreeDeleteCosts(F1);
	distance->UpdateTreeDeleteCosts(G1);
	//which tree is initially bigger
	if(F1->getSize() > G1->getSize())
	{
		initReverse = false;
	}
	else
	{
		initReverse = true;
	}
	//give an index to each node in each tree, 0 - F tree, 1 - Gtree.
	F1->PostOrderUpdateGetTree(0);
	G1->PostOrderUpdateGetTree(1);
	F=F1;
	G=G1;
	delta=new int*[F1->getSize()+2];
	for(int i=1; i<F1->getSize()+2 ; i++)
	{
		delta[i]=new int[G1->getSize()+2];
		//Calculate the delta between each leaf in G (empty tree) and all the nodes in F
		for(int j=1; j<G1->getSize()+2 ; j++)
		{
			if(Tree::GetTree[1][j]->getRight() == NULL && Tree::GetTree[0][i]->getRight() == NULL)
				delta[i][j] = 0;
			else
			{
				if(Tree::GetTree[1][j]->getRight() == NULL)
					delta[i][j] = distance->DeleteTree(Tree::GetTree[0][i]);
				if(Tree::GetTree[0][i]->getRight() == NULL)
					delta[i][j] = distance->DeleteTree(Tree::GetTree[1][j]);
			}
		}
	}
	//Klien decides the strategy only via the initially bigger tree.
	if(algorithm == KLIEN)
	{
		if(G1->getSize() > F1->getSize())
		{
			//calculate the Left/Right Subforest Enumerations for G needed for Klien and Shasha&zhang
			startLse = new Lse(F1, distance);
			startRse = new Rse(F1, distance);
			TED_pro(G1,F1,true);
		}
	}
	if(algorithm != OPT)
	{
		//calculate the Left/Right Subforest Enumerations for G needed for Klien and Shasha&zhang
		startLse = new Lse(G1, distance);
		startRse = new Rse(G1, distance);
	}
	TED_pro(F1,G1,false);
}



TED::~TED()
{
	for(int i=1; i<F->getSize()+2 ; i++)
	{
		delete[] delta[i];
	}
	delete[] delta;
	if(!Tree::GetTree[0].empty())
		Tree::GetTree[0].clear();
	if(!Tree::GetTree[1].empty())
		Tree::GetTree[1].clear();
}



void TED::TED_pro(Tree *F1, Tree *G1, bool reversed)
{
	if((algorithm == OPT) && (F1->getSize() < G1->getSize())) // used only by OPT
		TED_pro(G1,F1,!reversed);
	else
	{
		Tree* Heavy = F1;
		if(algorithm == SHASHA_ZHANG) //Shasha and Zhang keep the strategy left during the whole run
			F1->SelectRightHeavyPath();
		else
			F1->FindHeavyPath();
		while(Heavy!=NULL)
		{
			for(int i = Heavy->getChildrenCount()-1; i>=0 ; i--)
			{
				if(!Heavy->getChild(i)->getData()->getHeavy())
					TED_pro(Heavy->getChild(i), G1, reversed);
			}
			Heavy = Heavy->getHeavy();
		}
		ComputePeriodMain(F1,G1,reversed);
		F1->ClearHeavyPath();
	}	
}

void TED::ComputePeriodMain(Tree* F1, Tree* G1, bool reversed)
{
	Lse* lse;
	Rse* rse;
	vector<int>* T;
	T = new vector<int>[G1->getSize()+1];//represents i in G1(i,j) from 0 to G1->getSize()
	if(algorithm != OPT && G1->getSize() == G->getSize())
	{
		lse = startLse;
		rse = startRse;
	}
	else
	{
		lse = new Lse(G1, distance);
		rse = new Rse(G1, distance);
	}
	PrecomputeT(T, *lse);
	if(F1->getHeavy() == NULL)
		ComputePeriodRec( F1, G1, reversed, T, LEFT, *lse, *rse);
	else
	{
		if(F1->getRight()->getData()->getHeavy())// the right child is the heavy child
			ComputePeriodRec( F1, G1, reversed, T, LEFT, *lse, *rse);
		else
			if(F1->getLeft()->getData()->getHeavy())// the left child is the heavy child
				ComputePeriodRec( F1, G1, reversed, T, RIGHT, *lse, *rse);
			else//there are 2 directions left and right
				ComputePeriodRec( F1, G1, reversed, T, BOTH, *lse, *rse);
	}
	result=T[0][0];
	delete[] T;
}	

void TED::ComputePeriodRec(Tree *F1, Tree *G1, bool reversed, vector<int> *T, Strategy dir, Lse& lse, Rse& rse)
{
	if(F1->getHeavy()==NULL)//leaf
		ComputePeriod(F1,G1,reversed,T,dir,lse,rse,false);
	else
	{
		if(dir==RIGHT)
		{
			if(F1->getHeavy()->getHeavy()==NULL)//height=1
			{
				ComputePeriodRec(F1->getHeavy(),G1,reversed,T,LEFT,lse,rse);
				rse.Convert(T, lse);
			}
			else
			{
				if(F1->getHeavy()->getRight()->getData()->getHeavy())// the right child is the heavy child
				{
					ComputePeriodRec( F1->getHeavy(), G1, reversed, T, LEFT, lse, rse);
					rse.Convert(T, lse);
				}
				else
				{
					if(F1->getHeavy()->getLeft()->getData()->getHeavy())
						ComputePeriodRec( F1->getHeavy(), G1, reversed, T, RIGHT, lse, rse);
					else
						ComputePeriodRec( F1->getHeavy(), G1, reversed, T, BOTH, lse, rse);
				}
			}
		}
		else
		{
			if(dir==LEFT)
			{
				if(F1->getHeavy()->getHeavy()==NULL)//height=1
				{
					ComputePeriodRec(F1->getHeavy(),G1,reversed,T,LEFT,lse,rse);
				}
				else
				{
					if(F1->getHeavy()->getRight()->getData()->getHeavy())
						ComputePeriodRec(F1->getHeavy(),G1,reversed,T,LEFT, lse, rse);
					else
					{
						if(F1->getHeavy()->getLeft()->getData()->getHeavy())
						{
							ComputePeriodRec(F1->getHeavy(),G1,reversed,T,RIGHT, lse, rse);
							lse.Convert(T,rse);
						}
						else
						{
							ComputePeriodRec(F1->getHeavy(),G1,reversed,T,BOTH, lse, rse);
							lse.Convert(T,rse);
						}
					}
				}
			}
			else//dir==BOTH
			{
				if(F1->getHeavy()->getHeavy()==NULL)//height=1
				{
					ComputePeriodRec(F1->getHeavy(),G1,reversed,T,LEFT,lse,rse);
				}
				else
				{
					if(F1->getHeavy()->getRight()->getData()->getHeavy())
						ComputePeriodRec(F1->getHeavy(),G1,reversed,T,LEFT, lse, rse);
					else
					{
						if(F1->getHeavy()->getLeft()->getData()->getHeavy())
						{
							ComputePeriodRec(F1->getHeavy(),G1,reversed,T,RIGHT, lse, rse);
							lse.Convert(T,rse);
						}
						else
						{
							ComputePeriodRec(F1->getHeavy(),G1,reversed,T,BOTH, lse, rse);
							lse.Convert(T,rse);
						}
					}
				}
			}
		}
		if(dir!=BOTH)
			ComputePeriod(F1,G1,reversed,T,dir,lse,rse,false);
		else
		{
			ComputePeriod(F1,G1,reversed,T,LEFT,lse,rse,true);
			rse.Convert(T,lse);
			ComputePeriod(F1,G1,reversed,T,RIGHT,lse,rse,false);
		}
	}
}

void TED::ComputePeriod(Tree* Fvp, Tree* G1, bool reversed, vector<int>* T, Strategy dir, Lse& lse, Rse& rse, bool FirstSideOf2)
{
	if(Fvp->getSize()==0)
	{
		int Q;
		for(int i=G1->getSize(); 0<=i ; i--)
		{
			int JofI = lse.get_JofI(i);
			int *S = new int[JofI+1];
			for(int j=JofI ; 0<=j ; j--)
			{
				int arg1,arg2,arg3;
				arg1 = distance->DeleteNode(Fvp) + T[i][j];
				if(j==JofI)//arg2
				{
					if(i+JofI == G1->getSize())
						arg2 = distance->DeleteNode(G1) + distance->DeleteNode(Fvp);
					else
						arg2 = distance->DeleteNode(G1) + Q;
				}
				else
				{
					arg2 = distance->DeleteNode(G1) + S[j+1];
				}
				arg3 = distance->MatchNodes(Fvp, lse.GetForest(i,j)) -
					 distance->DeleteNode(lse.GetForest(i,j)) + lse.getForestSize(i,j);
				S[j]=Minimum(arg1,arg2,arg3);
			}
			for(int j=0; j<=JofI ; j++)
			{
				T[i][j] = S[j];
			}
			if(i!=0)
			{
				int j = lse.get_JofI(i-1);
				if(j <= JofI)
					Q = S[j];
			}
			delete[] S;
		}
	}
	else
	{
		if(dir==LEFT)
		{
			Ilse ilse(Fvp, distance);
			int* Q;
			int leftSize(0); //left tree size
			int deltaIn;
			if(Fvp->getLeft()==NULL)
				leftSize = 0;
			else
			{
				for(int k=0; !Fvp->getChild(k)->getData()->getHeavy() ; k++)
					leftSize += Fvp->getChild(k)->getSize()+1;
			}
			Q = new int[leftSize+2];	//Q[0] = empty. size of Q = size of the left tree + Fvp + right son of Fvp
			//Fix attempt
			if(G1->getSize() != 0 && ilse.get_Fk(1)->getData()->getLabel() == Fvp->getData()->getLabel())
			{
				int deltaIn = T[1][0];
				if(reversed)//the difference is in delta
				{
					delta[lse.GetForest(0,0)->getData()->getIndex()][ilse.get_Fk(1)->getData()->getIndex()] = deltaIn;
				}
				else
				{
					delta[ilse.get_Fk(1)->getData()->getIndex()][lse.GetForest(0,0)->getData()->getIndex()] = deltaIn;
				}
			}
			for(int i=G1->getSize(); 0<=i ; i--)
			{
				int** S;
				int JofI = lse.get_JofI(i);
				S = new int*[leftSize+2];//S[0] = empty.
				for(int k=1; k<=leftSize+1 ; k++)
				{
					S[k] = new int[JofI+1];
				}
				for(int k=1; k<=leftSize+1 ; k++)
				{
					for(int j=JofI ; 0<=j ; j--)
					{
						int arg1,arg2,arg3;
						//Calculate Table S using dynamic programming
						if(k==1)//arg1
						{
							arg1 = distance->DeleteNode(Fvp) + T[i][j];
						}
						else
						{
							arg1 = distance->DeleteNode(Fvp) + S[k-1][j];
						}
						if(j==JofI)//arg2
						{
							if(i+JofI == G1->getSize())
							{
								arg2 = distance->DeleteNode(G1) + ilse.get_Fk(k)->getData()->getDC();
							}
							else
							{
								arg2 = distance->DeleteNode(G1) + Q[k];
							}
						}
						else
						{
							arg2 = distance->DeleteNode(G1) + S[k][j+1];
						}
						arg3 = distance->MatchNodes(ilse.get_Fk(k), lse.GetForest(i,j));//arg3
						if(reversed)//the difference is in delta
						{
							arg3 += delta[lse.GetForest(i,j)->getData()->getIndex()][ilse.get_Fk(k)->getData()->getIndex()];
						}
						else
						{
							arg3 += delta[ilse.get_Fk(k)->getData()->getIndex()][lse.GetForest(i,j)->getData()->getIndex()];
						}
						if(j!=JofI)
						{
							if(k!=leftSize+1)
							{
								if(k == ilse.get_Fk(k)->getSize()+1)
									arg3 += T[i][j+lse.GetForest(i,j)->getSize()+1];
								else
									arg3 += S[k-ilse.get_Fk(k)->getSize()-1][j+lse.GetForest(i,j)->getSize()+1];
							}
							else
								arg3 += lse.getForestSize(i,j) - lse.GetForest(i,j)->getData()->getDT();
						}
						else
						{
							if(k!=leftSize+1)
								arg3 += ilse.get_Fk(k-ilse.get_Fk(k)->getSize()-1)->getData()->getDC();
						}
						S[k][j] = Minimum(arg1,arg2,arg3);
					}
				}
				if(i!=0)
				{
					if(i+lse.get_JofI(i-1) <= G1->getSize())
					{
						if(leftSize==0)
							deltaIn = T[i][lse.get_JofI(i-1)];
						else
							deltaIn =  S[leftSize][lse.get_JofI(i-1)];
					}
					else
					{
							deltaIn = -1;
					}
					for(int k=1 ; k<=leftSize+1 ; k++)
					{
						int j = lse.get_JofI(i-1);
						if(j <= JofI)
							Q[k] = S[k][j];
					}
					if(reversed)
					{
						if(deltaIn != -1)
							delta[lse.GetForest(i-1,lse.get_JofI(i-1))->getData()->getIndex()][Fvp->getData()->getIndex()] = deltaIn;
					}
					else
					{
						if(deltaIn != -1)
							delta[Fvp->getData()->getIndex()][lse.GetForest(i-1,lse.get_JofI(i-1))->getData()->getIndex()] = deltaIn;
					}
				}
				for(int j=0; j<=JofI; j++)
				{
					if(FirstSideOf2)//compute T for Fvp-1 instead of Fvp to such that T will be correct for the other direction
						T[i][j] = S[leftSize][j];
					else
						T[i][j] = S[leftSize+1][j];
				}
				for(int k=1; k<=leftSize+1 ; k++)
				{
					delete[] S[k];
				}
				delete[] S;
			}
		}
		else
		{
			Irse irse(Fvp , distance);
			int rightSize(0);
			int deltaIn;
			if(Fvp->getRight()==NULL)
				rightSize=0;
			else
			{
				for(int k=Fvp->getChildrenCount()-1; !Fvp->getChild(k)->getData()->getHeavy() ; k--)
					rightSize += Fvp->getChild(k)->getSize()+1;
			}
			int* Q = new int[rightSize+2];	//Q[0] = empty. size of Q = size of the right tree + Fvp + left son of Fvp
			//Fix attempt
			if(G1->getSize() != 0 && irse.get_Fk(1)->getData()->getLabel() == Fvp->getData()->getLabel())
			{
				int deltaIn = T[1][0];
				if(reversed)//the difference is in delta
				{
					delta[rse.GetForest(0,0)->getData()->getIndex()][irse.get_Fk(1)->getData()->getIndex()] = deltaIn;
				}
				else
				{
					delta[irse.get_Fk(1)->getData()->getIndex()][rse.GetForest(0,0)->getData()->getIndex()] = deltaIn;
				}
			}
			for(int i=G1->getSize(); 0<=i ; i--)
			{
				int** S;
				int JofI = rse.get_JofI(i);
				S = new int*[rightSize+2];//S[0] = empty.
				for(int k=1; k<=rightSize+1 ; k++)
				{
					S[k] = new int[JofI+1];
				}
				for(int k=1; k<=rightSize+1 ; k++)
				{
					for(int j=JofI ; 0<=j ; j--)
					{
						int arg1,arg2,arg3;
						//Calculate Table S using dynamic programming
						if(k==1)//arg1
						{
							arg1 = distance->DeleteNode(Fvp) + T[i][j];
						}
						else
						{
							arg1 = distance->DeleteNode(Fvp) + S[k-1][j];
						}
						if(j==JofI)//arg2
						{
							if(i+JofI == G1->getSize())
							{
								arg2 = distance->DeleteNode(G1) + irse.get_Fk(k)->getData()->getDC();
							}
							else
							{
								arg2 = distance->DeleteNode(G1) + Q[k];
							}
						}
						else
						{
							arg2 = distance->DeleteNode(G1) + S[k][j+1];
						}
						arg3 = distance->MatchNodes(irse.get_Fk(k), rse.GetForest(i,j)); //arg3
						if(reversed)//the difference is in delta
						{
							arg3 += delta[rse.GetForest(i,j)->getData()->getIndex()][irse.get_Fk(k)->getData()->getIndex()];
						}
						else
						{
							arg3 += delta[irse.get_Fk(k)->getData()->getIndex()][rse.GetForest(i,j)->getData()->getIndex()];
						}
						if(j!=JofI)
						{
							if(k!=rightSize+1)
							{
								if(k != irse.get_Fk(k)->getSize()+1) //Fk - Right(Fk) = Fvp without its right sons tree and the root
									arg3 += S[k-irse.get_Fk(k)->getSize()-1][j+rse.GetForest(i,j)->getSize()+1];
								else
									arg3 += T[i][j+rse.GetForest(i,j)->getSize()+1];
							}
							else
								arg3 += rse.GetForestSize(i,j) - rse.GetForest(i,j)->getData()->getDT();
						}
						else
						{
							if(k!=rightSize+1)
								arg3 += irse.get_Fk(k-irse.get_Fk(k)->getSize()-1)->getData()->getDC();
						}
						S[k][j] = Minimum(arg1,arg2,arg3);
					}
				}
				
				if(i!=0)
				{
					if(i+rse.get_JofI(i-1) <= G1->getSize())
					{
						if(rightSize==0)
							deltaIn = T[i][rse.get_JofI(i-1)];
						else
							deltaIn = S[rightSize][rse.get_JofI(i-1)];
					}
					else
					{
							deltaIn = -1;
					}
					for(int k=1 ; k<=rightSize+1 ; k++)
					{
						int j = rse.get_JofI(i-1);
						if(j <= JofI)
							Q[k] = S[k][j];
					}
					if(deltaIn != -1)
					{
						if(reversed)
						{
							delta[rse.GetForest(i-1,rse.get_JofI(i-1))->getData()->getIndex()][Fvp->getData()->getIndex()] = deltaIn;
						}
						else
						{
							delta[Fvp->getData()->getIndex()][rse.GetForest(i-1,rse.get_JofI(i-1))->getData()->getIndex()] = deltaIn;
						}
					}
				}
				for(int j=0; j<=JofI; j++)
				{
					if(FirstSideOf2)//compute T for Fvp-1 instead of Fvp to such that T will be correct for the other direction
						T[i][j] = S[rightSize][j];
					else
						T[i][j] = S[rightSize+1][j];
				}
				for(int k=1; k<=rightSize+1 ; k++)
				{
					delete[] S[k];
				}
				delete[] S;
			}
		}
	}
}
	


void TED::PrecomputeT(vector<int>* T, Lse& lse)
{
	for(int i=0; i < lse.GetT()->getSize()+1; i++)//precompute T for the first period
	{
		int JofI=lse.get_JofI(i);
		for(int j=0; j<=JofI ; j++)
		{
			T[i].push_back(lse.getForestSize(i,j));
		}
	}
}
